#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct BinaryTreeNode
{
	int data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTnode;

BTnode* BinaryTreeNodeCreate(int x)
{
	BTnode* treenode = malloc(sizeof(BTnode));
	if (treenode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	treenode->data = x;
	treenode->left = NULL;
	treenode->right = NULL;

	return treenode;
}

void BTPrevOrder(BTnode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%d ", root->data);
	BTPrevOrder(root->left);
	BTPrevOrder(root->right);
}

void BTInOrder(BTnode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	BTPrevOrder(root->left);
	printf("%d ", root->data);
	BTPrevOrder(root->right);
}

void BTPostOrder(BTnode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	BTPrevOrder(root->left);
	printf("%d ", root->data);
	BTPrevOrder(root->right);
}

int BTNodeNum(BTnode* root)
{
	return root == NULL ? 0 : BTNodeNum(root->left) + BTNodeNum(root->right) + 1;
}

int BTLeftNum(BTnode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}

	return BTLeftNum(root->left) + BTLeftNum(root->right);
}

int main()
{
	BTnode* n1 = BinaryTreeNodeCreate(1);
	BTnode* n2 = BinaryTreeNodeCreate(2);
	BTnode* n3 = BinaryTreeNodeCreate(3);
	BTnode* n4 = BinaryTreeNodeCreate(4);
	BTnode* n5 = BinaryTreeNodeCreate(5);
	BTnode* n6 = BinaryTreeNodeCreate(6);
	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->left = n5;
	n4->right = n6;

	BTPrevOrder(n1);
	printf("\n");
	BTInOrder(n1);
	printf("\n");
	BTPostOrder(n1);
	printf("\n");

	printf("%d\n", BTNodeNum(n1));
	printf("%d\n", BTLeftNum(n1));

	return 0;
}








